异色弧

Time Limit: 20 Sec Memory Limit: 256 MB

Description

img

Input

img

Output

仅一行一个整数表示答案。

Sample Input

8
　　1 2 3 1 2 3 2 1

Sample Output

8

HINT

img

Main idea

给定若干个点，每个点有一个颜色，颜色一样的可以组成一个区间，询问有几个交。

Solution

BearChild只会70分的做法，记录N表示区间个数，效率为O(Nlog(N))。这里介绍一下。

我们基于将所有区间提取出来计算，可以用一个vector存一下记录相同颜色的，然后相同颜色的任意组合即可组成可行的区间。

首先我们考虑容斥：颜色不同的相交个数 = 不考虑颜色的总相交个数 - 颜色相同的相交个数。然后我们分段来解：

1. 不考虑颜色的总相交个数：
　　　　我们考虑带log的算法，先将所有区间按照右端点（细节：若相同则将左端点大的放在前面，保证不会算入答案）排序，然后顺序往后做，每次用树状数组在区间左端点+1，区间(右端点-1)处-1（细节：右端点-1处是为了处理前一个的右端点=这一个的左端点情况），然后每次只要查询(左端点-1)的前缀和，显然就是在这个区间前和这个区间的交的个数。这样我们就可以计算出总相交个数了。

2.颜色相同的相交个数：
　　　　我们考虑如何计算颜色相同的相交个数，设a表示一个颜色的个数，显然个数就是：C(a,4)。也就是任意4个相同颜色点可以组成一个交。

然后我们相减一下，就可以得到答案啦。注意一下细节。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<bits/stdc++.h>
using namespace std;

typedef long long s64;
const int ONE = 100010;
const int MOD = 1e9+7;

vector <int> q[ONE];

int n;
int A[ONE];
int cnt,Ans;
int Max,vis[ONE];
int Jc[ONE],inv[ONE];

struct power
{
    int l,r;
}a[20000001];

bool cmp(const power &a,const power &b)
{
    if(a.r == b.r) return a.l > b.l;
    return a.r < b.r;
}

void Moit(int &a)
{
    if(a<MOD) a+=MOD;
    if(a>MOD) a-=MOD;
}

int get()
{
    int res=1,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

namespace D
{
    int Quickpow(int a,int b)
    {
        int res=1;
        while(b)
        {
            if(b&1) res=(s64)res*a%MOD;
            a=(s64)a*a%MOD;
            b>>=1;
        }
        return res;
    }

    void Deal_Jc(int k)
    {
        Jc[0]=1;
        for(int i=1;i<=k;i++) Jc[i] = (s64)Jc[i-1]*i%MOD;
    }

    void Deal_inv(int k)
    {
        inv[0]=1;    inv[k] = Quickpow(Jc[k],MOD-2);
        for(int i=k-1;i>=1;i--) inv[i] = (s64)inv[i+1]*(i+1)%MOD;
    }

    void pre(int k)
    {
        Deal_Jc(k);    Deal_inv(k);
    }
}

int C(int n,int m)
{
    if(n < m) return 0;
    return (s64)Jc[n]*inv[m]%MOD*inv[n-m]%MOD;
}

namespace Bit
{
    int C[ONE];

    int lowbit(int x)
    {
        return x&-x;
    }

    void Add(int R,int x)
    {
        for(int i=R;i<=n;i+=lowbit(i))
            C[i]+=x, Moit(C[i]);
    }

    int Query(int R)
    {
        int res=0;
        for(int i=R;i>=1;i-=lowbit(i))
            res+=C[i], Moit(res);
        return res;
    }
}

int main()
{
    n=get();    D::pre(n+1);
    for(int i=1;i<=n;i++)
    {
        A[i]=get();
        q[A[i]].push_back(i);
        Max=max(Max,A[i]);
    }
    for(int k=1;k<=Max;k++)
    {
        if(!q[k].size()) continue;
        Ans-=C(q[k].size(),4);    Moit(Ans);
        for(int i=0;i< q[k].size();i++)
            for(int j=i+1;j< q[k].size();j++)
                a[++cnt].l=q[k][i], a[cnt].r=q[k][j];
    }

    sort(a+1,a+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
    {
        Ans += Bit::Query(a[i].l-1);
        Moit(Ans);
        Bit::Add(a[i].l,1), Bit::Add(a[i].r-1,-1);
    }

    printf("%d",Ans);
}